package com.example.algorithm.huawei_rongyao_29;

import java.util.Scanner;

// 折纸问题
// 难度：简单

/**
 * 这个问题的首要思路是先弄清楚折纸折现的新增规律。然后发现这个新增的规律可以很好的使用二叉树来建模。
 * 可以使用递归来解决。每次对折纸条，相当于在已有的折痕上再做一次对折，而对折后的折痕顺序可以根据对称性来确定。
 * 首先，如果我们知道上一次对折的结果，那么这一次对折的结果就可以通过在上一次对折结果的两侧分别加上"down"和"up"来确定。(这就是中心对称性)
 * 例如，上一次对折结果为 ["down", "up"]，那么这一次对折的结果为 ["down", "down", "up", "up"]。
 * 递归的边界条件为 N=1，即对折一次的情况，结果只有一个折痕，方向为 "down"。
 * <p>
 * 实际经过测试，完全正确
 */
public class Q08_PaperFolding {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        printAllFolds(n);
        scanner.close();
    }

    //从上往下打印所有折痕方向
    public static void printAllFolds(int n) {
        // i是当前节点所在层数。传1是因为，printProcess目前接收的是根节点，所以i传1。
        // n是用户输入的，其实值折纸次数。同时也是树的总层数。
        // 第三个参数boolean是判断当前节点是否是down节点。根节点是down，所以传true。
        printProcess(1, n, true);
    }

    //递归过程，来到某一个节点，
    public static void printProcess(int i, int n, boolean isDown) {

        // i表示当前层。n表示总层数。i最大可以等于n。下面表示超过了深度
        if (i > n) {
            return;
        }
        //往下递归左节点。因为每个节点的左节点固定是down。所以，我们这里，直接把i+1,然后boolean传true，就模拟去到了当前节点的左节点。
        // 一旦进去下面这句，那么，会一直递归进入到最深一层的左节点。然后下面这句代码所代表的递归进入过程才结束。
        printProcess(i + 1, n, true);
        // 上面的一直深入进最底层找左节点的过程结束之后。其实就是找到了二叉树的最底层最靠左的那个节点。
        // 打印当前层函数上下文中接收到的isDown变量的具体值。
        // isDown是布尔值，转换为字符串。
        System.out.println(isDown ? "down" : "up");
        //往下递归，up节点
        printProcess(i + 1, n, false);
    }
}


